package com.zhugang.week13.slidingwindow;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @program algorithms
 * @description: findContinuousSequence
 * @author: chanzhugang
 * @create: 2022/09/19 11:10
 */
public class FindContinuousSequence {

    /**
     * 剑指offer 57-II 和为s的连续正数序列
     * https://leetcode.cn/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/
     *
     * @param target
     * @return
     */
    public int[][] findContinuousSequence(int target) {
        // 连续正数序列：想到滑动窗口，类似双指针
        int i = 1;
        int j = 2;
        int sum = 3;
        List<int[]> result = new ArrayList<>();
        while (i < j) {
            if (sum == target) {
                // 找到一组解
                int[] array = new int[j - i + 1];
                for (int k = i; k <= j; k++) {
                    array[k - i] = k;
                }
                result.add(array);
                // i、j一起向右滑动；左区间-；右区间+
                sum -= i;
                i++;
                j++;
                sum += j;
            } else if (sum < target) {
                // 右区间+
                j++;
                sum += j;
            } else {
                // 左区间-
                sum -= i;
                i++;
            }
        }

        int[][] arrResult = new int[result.size()][];
        for (int k = 0; k < result.size(); k++) {
            arrResult[k] = result.get(k);
        }
        return arrResult;
    }


    // 此种解法代码更简洁：推荐
    public int[][] findContinuousSequence2(int target) {
        // 双指针法
        List<int[]> result = new ArrayList<>();
        for (int l = 1, r = 2; l < r; ) {
            // 等差数列求和公式
            int sum = (l + r) * (r - l + 1) / 2;
            if (sum == target) {
                int[] arr = new int[r - l + 1];
                for (int i = l; i <= r; i++) {
                    arr[i - l] = i;
                }
                result.add(arr);
                l++;
            } else if (sum < target) {
                r++;
            } else {
                l++;
            }
        }
        return result.toArray(new int[result.size()][]);
    }

    public int[][] findContinuousSequence3(int target) {
        // 滑动窗口 + 求和公式
        int l = 1;
        int r = 2;
        List<int[]> result = new ArrayList<>();
        while (l < r) {
            int sum = (l + r) * (r - l + 1) / 2;
            if (sum == target) {
                int[] arr = new int[r - l + 1];
                for (int i = l; i <= r; i++) {
                    arr[i - l] = i;
                }
                result.add(arr);
                l++;
            } else if (sum < target) {
                r++;
            } else {
                l++;
            }
        }
        // 集合转数组
        return result.toArray(new int[result.size()][]);
    }
}